In the digital reproduction of documents, image information, be it color, black or white, is commonly generated in a bitmap format where the bitmap comprises a plurality of continuous tone or gray level pixels, i.e. pixels that are defined by digital values, each value representing a gray level among a number of gray levels. Thus, in an 8 bit system, 256 levels of gray are present, where each level represents an increment of gray between black and white. In the case of color bitmaps, where three defining colors or separations each include 256 levels of information, there may be more than 16 million colors defined by a gray bitmap.
Usually, bitmaps in such a gray level format are unprintable by standard printers. Standard printers print in a limited number of levels, either a spot or a no spot in the binary case, or a limited number of levels associated with the spot, for example, four in the quaternary case. Accordingly, it is necessary to reduce or quantize the gray level image data to a limited number of levels so that it is printable. Besides gray level information derived by scanning, certain processing techniques such as those described, for example, in U.S. Pat. No. 5,226,094 to Eschbach may produce gray level data requiring quantization for printing.
One standard method of quantizing gray level pixel values to binary level pixel values is through the use of dithering or screening processes. In such arrangements, over a given area having a number of gray pixels therein, each pixel value of an array of gray level pixels within the area is compared to one of a set of preselected thresholds (the thresholds are stored as a screen matrix and the repetitive pattern generated by this matrix is considered a screen cell) as taught, for example, in U.S. Pat. No. 4,149,194 to Holladay. The effect of such an arrangement is that, for an area where the image is gray, some of the thresholds within the screen matrix will be exceeded, i.e. the image value at that specific location is larger than the value stored in the dither matrix for that same location, while others are not. In the binary case, the pixels or cell elements for which the thresholds are exceeded might be printed as black, while the remaining elements are allowed to remain white, dependent on the actual physical quantity described by the data. The effect of the distribution of black and white over the halftone cell is integrated by the human eye as gray. A trade off is required between the number of gray level increments representable by a screen cell, versus the size or frequency of the cell. While it is desirable to have as many gray levels as possible representable by a screen cell, such a requirements increases the size of the cell until its repetition across an image becomes visible. However, with a smaller cell, which can be repeated at high frequency across a page, only a relatively small number of gray levels can be represented.
Algorithms that convert gray images to binary or other number of level images without repeating patterns exist, and include among them error diffusion, as taught, for example, in "An Adaptive Algorithm for Spatial Greyscale" by Floyd and Steinberg, Proceedings of the SID 17/2, 75-77 (1976) (hereinafter, "Floyd and Steinberg"). Error diffusion attempts to maintain image density by making the conversion from gray pixels to binary or other level pixels on a pixel-by-pixel basis. The procedure examines each pixel with respect to a threshold, and the difference between the gray level pixel value and the output value is forwarded to a selected group or set of neighboring pixels, in accordance with a weighting scheme. Another, more elaborate method would be the error diffusion techniques of U.S. Pat. No. 5,045,952 to Eschbach, which serves to provide image dependent edge enhancement. Additional modifications to the error diffusion algorithm taught by Floyd and Steinberg have been proposed, e.g.: a different weighting matrix, as taught, for example, in "A Survey of Techniques for the Display of Continuous Tone Pictures on Bilevel Displays" by Jarvis et al., Computer Graphics and Image Processing, Vol. 5., pp. 13-40 (1976) (hereinafter, Jarvis), and in "MECCA--A Multiple-Error Correction Computation Algorithm for Bi-Level Image Hardcopy Reproduction" by Stucki, IBM Res. Rep. RZ1060 (1981) (hereinafter, Stucki). Modifications of the error calculation and weight allocation have been taught, for example, in U.S. patent application Ser. No. 07/672,987 (with a counterpart application published in Japan at JP-A14-328957), entitled "Method for Image Conversion with Application of Multiple Error Diffusion Matrices", by Eschbach, U.S. Pat. No. 4,924,322 to Kurosawa et. al., U.S. 4,339,774 to Temple, U.S. Pat. No. 4,955,065, to Ulichney and U.S. patent application Ser. No. 08/167,758 by Shiau et al. Error diffusion tends to suffer from a characteristic "worming" defect.
One method of reducing the worming artifact in an error diffusion process that has been noted is to distribute error along a space filling curve, such as Hilbert, Peano or Murray Curves. See, for example, "Using Peano Curves for Bilevel Display of Continuous-Tone images", by Witten et al., IEEE Comp. Grah. and App. Vol. 2, No. 5, pp 47-52 (1982); "Naive Halftoning" by A. J. Cole, Proceedings of CGI '90, Springer Verlag pp. 203-222 (1990); and "Three Plus Five Makes Eight: A Simplified Approach to Halftoning" by Wyvill et al., Proceedings of CGI '91 Scientific Visualiation of Physical Phenomena pp. 379-392 (1991). Unfortunately, space filling curves presents complex processing order, see, for example, "Digital Halftoning with Space Filling Curves," by L. Velho et al., Computer Graphics, vol. 25, No. 4, pp. 81-90 (1991) while, in view of the operation of printers and most image processors, it would be highly desirable to work in scan line order.
Error diffusion is often unusable by certain reproduction processes, such as electrophotography, because it tends to produce isolated single spots that are not reproducible. In such cases, screening is used with threshold sets arranged to cluster spots together into larger printable dots. Error diffusion is also an inherently sequential process that does not lend itself to parallel processing, while screening.
All of the references cited herein are incorporated by reference for their teachings.